from BinaryTree import *


class LinkedBinaryTree(BinaryTree):
    """链式二叉树"""

    class _Node:
        __slots__ = '_element', '_parent', '_left', '_right'

        def __init__(self, element, parent=None, left=None, right=None):
            self._element = element
            self._parent = parent
            self._left = left
            self._right = right

    class Position(BinaryTree.Position):
        """每个位置是一个节点"""

        def __init__(self, container, node):
            self.container = container
            self._node = node

        def element(self):
            return self._node._element

        def __eq__(self, other):
            return type(other) is type(self) and other._node == self._node

    def validate(self, p):
        """判断是否是合法的位置对象，是则返回p的节点"""
        if not isinstance(p, self.Position):
            raise TypeError('p不是一个位置对象')
        if p.container is not self:
            raise ValueError('p不属于该树')
        if p._node._parent is p._node:
            raise ValueError('p is no longer valid')
        return p._node

    def make_position(self, node):
        return self.Position(self, node) if node is not None else None

    # --------------------------构造函数---------------------------------
    def __init__(self):
        self._root = None
        self.size = 0

    # --------------------------公共方法---------------------------------
    def __len__(self):
        return self.size

    def root(self):
        return self.make_position(self._root)

    def parent(self, p):
        node = self.validate(p)
        return self.make_position(node._parent)

    def left(self, p):
        node = self.validate(p)
        return self.make_position(node._left)

    def right(self, p):
        node = self.validate(p)
        return self.make_position(node._right)

    def num_children(self,p):
        node = self.validate(p)
        count = 0
        if node._left is not None:
            count += 1
        if node._right is not None:
            count += 1
        return count

    def is_leaf(self, p):
        return self.num_children(p) == 0

    def add_root(self, e):
        if self._root is not None:
            raise ValueError('root已存在')
        self.size = 1
        self._root = self._Node(e)
        return self.make_position(self._root)

    def add_left(self, p, e):
        p_node = self.validate(p)
        if p_node._left is not None:
            raise ValueError('left 已存在')
        p_node._left = self._Node(e)
        self.size += 1
        return self.make_position(p_node._left)

    def add_right(self, p, e):
        p_node = self.validate(p)
        if p_node._right is not None:
            raise ValueError('right 已存在')
        p_node._right = self._Node(e)
        self.size += 1
        return self.make_position(p_node._right)

    def _delete(self, p):
        """删除位置p的节点，用他的一个子节点取代p，若p有两个子节点则报错"""
        p_node = self.validate(p)
        if self.num_children(p) == 0:
            raise ValueError('p 有两个子节点')

        if p_node._left is not None:
            child = p_node._left
        else:
            child = p_node._right

        if child is not None:
            child._parent = p_node._parent
        if p_node is self._root:
            self._root = child
        else:
            parent = p_node._parent
            if p_node is parent._left:
                parent._left = child
            else:
                parent._right = child
        self.size -= 1
        p_node._parent = p_node
        return p_node._element

    def _attach(self, p, t1 , t2):
        """将树t1，t2分别连接到p的后面"""
        p_node = self.validate(p)
        if not self.is_leaf(p):
            raise ValueError('p不是叶子节点')

        if not type(t1) is type(t2):
            raise TypeError('p或t1或t2不是树类型')
        self.size += len(t1) + len(t2)
        if not t1.is_empty():
            t1._root._parent = p_node
            p_node._left = t1._root
            t1._root = None
            t1.size = 0
        if not t2.is_empty():
            t2._root._parent = p_node
            p_node._right = t2._root
            t2._root = None
            t2.size = 0


if __name__ == '__main__':
    T = LinkedBinaryTree()
    T.add_root(9)
    T.add_left(T.root(),2)
    T.add_right(T.root(),3)
    print(T)
    for e in T:
        print(e)